게임이론 유형

A는 maximize, B는 minimize하는 게임 유형

가장 기본적으로는 minimax dp로 풀 수 있다. 제로섬게임 또한 보통 minimax dp로 푼다 (BOJ19553 피자배틀)

그냥 DP는 재미가 없으므로 그리디한 방법을 찾아야하는 문제들이 많은데, 보통 가능한 움직임?이 짝수개 주어지고 선공A가 아무거나 선택하는게 최적전략이며(A와 B의 선택지가 다르면서 상호작용이 없는경우) B는 A가 선택한 움직임에 따라 맞춰 움직이게 된다. 이러한 '움직임'의 매칭으로 모델링한 후 풀 수 있는 경우가 많으며 많은경우 그 모델링의 결과가 흥미롭게 나온다.

그래프나 트리에서 쫓고 쫓기는 게임도 게임오버되는 시간을 최소화/최대화하는 문제로 볼 수 있는데, 이 때 종종 최적의 선택이 무한루프인 경우가 있다. 뇌피셜로는 DP로도 갱신전에 값을 다른변수에 모아두고, 계산중에는 inf나 뭐 적당한 항등원을 dp값에 할당해둠으로써 사이클인 경우 적당히 처리해줄 수 있을거같은데 정해는 보통 bfs로 게임종료상태부터 거꾸로 초기상태로 올라오는거다.(backward induction이라고 하는듯) BOJ16058, ABC209E Shiritori

• BOJ Absolute Game 직선위의 점들 가중치 완전최소매칭
• BOJ Min-Max Distance Game 모델링하면 완전그래프에서 Vertex Cover와 Independant Set이었나? 안풀고 답만봐서 기억이 안난다.
• Atcoder https://atcoder.jp/contests/arc122/tasks/arc122_d XOR Game 모델링하면 두수XOR형태가 나온다
• BOJ12265 Deceitful War 문제이해가 좀 골치아픈데 모델링하면 그럴듯한 로직이 나온다.
• 16311 Harry the Hamster
• https://codeforces.com/contest/1628/problem/D1

두 플레이어의 목적이 동일하면서 가능한 행동집합도 동일한 경우(Impartial Game)

스프라그 그런디 정리만 알면 대부분 해결가능하다. 22900처럼 그리디한 뭔가를 요구하는걸 섞는경우도 종종 있으니 만능이라기보단 사전지식정도?

두 플레이어의 목적이 동일하지만 가능한 행동집합이 다른 경우(Partial Game)

Impartial의 스프라그 그런디에 해당하는 이 분야의 사전지식은 BlueRed Hackenbush이다. 딱 봐도 Impartial보다는 Partial이 더 어려운게 맞고, 모든 Partial이 헤켄버시로 항상 Reduction 가능한거도 아니다. BOJ22883 등